（1）找出数组中重复的数字
题目
在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组 {2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
解法1[Java]：动态重排序加判断
把值为 i 的元素放到第 i 个位置上去，如果它和第 i 个位置上的元素值相等，那么可以判断这个元素是重复的。
public class Solution {
public boolean duplicate(int[] numbers, int length, int[] duplication) {
// check whether the array is valid
if (numbers == null || length <= 0)
return false;
for (int i = 0; i < length; i++) {
if (numbers[i] < 0 || numbers[i] > length - 1) {
return false;
}
}
for (int i = 0; i < length; i++) {
if (numbers[i] != i) {
if (numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[i];
return true;
}
swap(numbers, i, numbers[i]);
}
}
return false;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
复杂度分析
时间复杂度为 。由于是直接对原数组进行操作，空间复杂度为 。
解法2[Java]：排序然后判断
解法3[Java]：使用Hash数据结构
总结
解法1只适合对数字型问题进行查找重复。解法2和解法3还可以用于对象的查找重复。
（2）不修改数组找出重复的数字
题目
在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
解法1[C++]：数数判定
#include <iostream>
int countRange(const int* numbers, int length, int start, int end);
// 参数:
// numbers: 一个整数数组
// length: 数组的长度
// 返回值:
// 正数 - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
// 负数 - 输入无效，或者数组中没有重复的数字
int getDuplication(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;
int start = 1;
int end = length - 1;
while(end >= start)
{
int middle = ((end - start) >> 1) + start;
int count = countRange(numbers, length, start, middle);
if(end == start)
{
if(count > 1)
return start;
else
break;
}
if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}
int countRange(const int* numbers, int length, int start, int end)
{
if(numbers == nullptr)
return 0;
int count = 0;
for(int i = 0; i < length; i++)
if(numbers[i] >= start && numbers[i] <= end)
++count;
return count;
}